// https://leetcode.cn/problems/palindrome-partitioning-iv/description/

// 算法思路总结：
// 1. 预处理所有子串的回文状态
// 2. 枚举两个分割点将字符串分为三部分
// 3. 检查三个部分是否均为回文串
// 4. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool checkPartitioning(string s) 
    {
        int m = s.size(), ret = 0;
        if (m < 2) return false;
        vector<vector<bool>> dp(m, vector<bool>(m, false));

        for (int i = m - 1; i >= 0; i--) 
        {
            for (int j = i; j < m; j++) 
            {
                if (s[i] == s[j]) 
                {
                    if (i == j)
                        dp[i][j] = true;
                    else if (i + 1 == j)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }

        for (int i = 1 ; i < m - 1 ; i++)
        {
            for (int j = i ; j < m - 1 ; j++)
            {
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][m - 1])
                    return true;
            }
        }

        return false;
    }
};

int main()
{
    string s1 = "abcbdd", s2 = "bcbddxy";
    Solution sol;

    cout << sol.checkPartitioning(s1) << endl;
    cout << sol.checkPartitioning(s2) << endl;

    return 0;
}

